package Union_Set;

//数组实现并查集
public  class UnionFind {
    // parent[i] = k ： i的父亲是k
    private int[] parent;
    // size[i] = k ： 如果i是代表节点，size[i]才有意义，否则无意义
    // i所在的集合大小是多少
    private int[] size;
    // 辅助结构,做栈使用
    private int[] help;
    // 一共有多少个集合
    private int sets;

    public UnionFind(int N) {
        parent = new int[N];
        size = new int[N];
        help = new int[N];
        sets = N;
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 从i开始一直往上，往上到不能再往上，代表节点，返回
    // 这个过程要做路径压缩
    private int findFather(int i) {
        int hi = 0;
        while (i != parent[i]) {
            //记录经过的所有节点位置
            help[hi++] = i;
            i = parent[i];
        }
        //路径压缩过程，将路过节点的parent更新
        for (hi--; hi >= 0; hi--) {
            parent[help[hi]] = i;
        }
        return i;
    }

    public void union(int i, int j) {
        int f1 = findFather(i);
        int f2 = findFather(j);
        if (f1 != f2) {
            //将size小的集合，挂载在size更大的集合上。
            if (size[f1] >= size[f2]) {
                size[f1] += size[f2];
                parent[f2] = f1;
            } else {
                size[f2] += size[f1];
                parent[f1] = f2;
            }
            sets--;
        }
    }

    public int sets() {
        return sets;
    }
}